Cho đến nửa cuối thế kỷ 19, vùng Lạng Sơn và Cao Bằng vẫn còn là những vùng núi hoang sơ biên viễn, là nơi cư trú của các dân tộc thiểu số hầu như không liên lạc với bên ngoài. Những tín đồ Công giáo đầu tiên của vùng này có lẽ là những người bị đi đày theo các chỉ dụ cấm đạo. Những ghi nhận đầu tiên ghi chép một tín đồ là ông phó Nhậm (phó lý trưởng), con của Thánh tử đạo Antôn Nguyễn Ðích bị đày lên Cao Bằng và một đại chủng sinh tên Trần Triêm (về sau được biết với tên gọi cụ sáu Trần Lục, hay linh mục Phêrô Trần Lục, người đã cho xây dựng nhà thờ đá Phát Diệm) bị đày lên Lạng Sơn vào năm 1858 thời Tự Ðức. Cho đến năm 1876, tại Cao Bằng có chừng 300 tín đồ, phần lớn là những người bị triều đình Huế phát vãng lên đây.

Ngày 13 tháng 6 năm 1881, một đoàn giáo sĩ gồm 2 linh mục và 3 thầy giảng do linh mục Fuentes (tên Việt: Phê), một thừa sai Ða Minh người Tây Ban Nha dẫn đầu, đã đến vùng này. Đoàn đã để lại một thầy giảng ở Cao Bằng và một linh mục ở Lạng Sơn.

Sau khi chiếm được quyền kiểm soát ở Bắc Kỳ, quân Pháp đã cho thiết lập nhiều đồn bót trên tuyến biên giới Việt-Trung. Để đáp ứng các nhu cầu tôn giáo, tháng 3 năm 1895, tòa Giám mục Bắc Ninh đã cử một linh mục lên Lạng Sơn làm tuyên úy và lập một nhà nguyện tại khu Văn Miếu, Cửa Nam, thị xã Lạng Sơn. Tại đây đã có chừng 50 giáo dân miền xuôi lên lập nghiệp.

Đầu thế kỷ 20, dưới áp lực của chính quyền thực dân Pháp, các giáo sĩ người Tây Ban Nha phải rời khỏi Việt Nam, để lại việc truyền giáo cho các đồng nghiệp người Pháp. Những cơ sở Công giáo đầu tiên được thành lập ở Bản Quấn, dưới chân núi Mẫu Sơn, tại Vườn Cam, thị xã Cao Bằng và Cao Bình, gần sông Bằng Giang.

Ngày 31 tháng 12 năm 1913, Tòa Thánh Roma ra sắc lệnh thành lập Hạt Phủ doãn Tông tòa Lạng Sơn, gồm hai tỉnh Cao Bằng, Lạng Sơn và một phần đất tỉnh Hà Giang (phía Ðông sông Lô). Phủ doãn Tông tòa Lạng Sơn được đặt dưới quyền coi sóc của Tỉnh Dòng Ða Minh Lyon. Bấy giờ, cả vùng Lạng Sơn–Cao Bằng có 12.000 người Kinh, 6.000 người Hoa, 270.000 người Tày và Nùng, 15.000 người Mông và người Dao. Tổng số khoảng 300.000 người.

Các Phủ doãn Tông tòa thời kỳ này gồm:

• Ðức ông Bertrand Cothonay Chiểu, O.P. (1913-1939).
• Ðức ông Marie Dominique Maillet Bính, O.P. (1925-1929).
• Ðức ông Félix Maurice Hedde Minh, O.P. (1929-1939).

Ngày 11 tháng 7 năm 1939, Hạt Phũ doãn Tông tòa được nâng lên thành Hạt Đại diện Tông tòa. Ngày 30 tháng 11 năm 1939, Ðức ông Hedde Minh được Khâm Sứ Tòa Thánh Drapier làm lễ tấn phong Giám mục. Ông được bổ nhiệm làm Đại diện Tông tòa Lạng Sơn. Ngày 6 tháng 7 năm 1948, Tòa Khâm sứ Huế thông báo tấn phong linh mục André Réginal Jacques Mỹ làm Giám mục Hiệu tòa Cerasa (Sades) và cử ông làm Phó Đại diện Tông tòa với quyền kế vị.

Do hoàn cảnh chiến tranh, đến năm 1958, hầu hết các giáo sĩ nước ngoài đều phải rời miền Bắc Việt Nam. Vùng Cao Bằng Lạng Sơn chỉ còn lại Giám mục Hedde Minh và 4 linh mục người Việt. Linh mục Vincent Phạm Văn Dụ được Tòa Thánh bổ nhiệm làm Tổng quản giáo phận sau đó phong ông là Giám mục hiệu tòa Boseta. Sau khi Giám mục Hedde Minh qua đời, ông là giáo sĩ cao cấp nhất coi sóc địa phận. Ngày 24 tháng 11 năm 1960, Giáo phận Lạng Sơn và Cao Bằng chính thức được thành lập và Giám mục Phạm Văn Dụ trở thành Giám mục chính tòa Lạng Sơn.